//在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“
//房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。 
//
// 计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 
//
// 示例 1: 
//
// 输入: [3,2,3,null,3,null,1]
//
//     3
//    / \
//   2   3
//    \   \ 
//     3   1
//
//输出: 7 
//解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 
//
// 示例 2: 
//
// 输入: [3,4,5,1,3,null,1]
//
//     3
//    / \
//   4   5
//  / \   \ 
// 1   3   1
//
//输出: 9
//解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
// 
// Related Topics 树 深度优先搜索 动态规划 二叉树 
// 👍 1021 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class HouseRobberIii {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(1);
        root.left = node1;root.right = node2;node1.left = node3;node1.right =node4;node2.right = node5;
        new HouseRobberIii().new Solution().rob(root);
    }
    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 这个题目的意思是，至少隔一个节点，也就是可以隔多个节点
     * 最直接的算一个节点能拿到的最大值为：
     * max(当前节点 + 四个孙子节点, 两个儿子节点)
     * 当计算当前节点能拿到多少钱时也计算出了子节点能拿多少，所以可以使用hashMap来存储数据，就不用重复迭代了
     * 以上这种写法是比较常规的思路
     *
     *
     * 还有一种解法，不用使用hashmap了
     * 当前节点能拿到的钱只有两种情况：
     *  1.当前节点不偷：左子节点能拿到的钱 + 右子节点能拿到的钱（左子节点和右子节点自己拿不拿无所谓）
     *  2.当前节点偷：当前节点的钱 + 左子节点不偷时能拿到的最大钱数 + 右子节点不偷时的最大钱数
     *  最终返回两种情况中较大的一种就行了
     *  使用int[2] 表示偷与不偷，0表示不偷 1表示偷
     *  这我是没想到的，看代码
     */
    public int rob(TreeNode root) {
        //Map<TreeNode,Integer> memo = new HashMap<>();
        //int res1 = count(root,memo);
        int[] result = countPlus(root);
        return Math.max(result[0], result[1]);
    }

    public int count(TreeNode node,Map<TreeNode,Integer> memo){
        if (node == null) return 0;
        if (memo.containsKey(node)) return memo.get(node);
        int money = node.val;
        if (node.left!=null) money += (count(node.left.left,memo)+count(node.left.right,memo));
        if (node.right!=null) money += (count(node.right.left,memo)+count(node.right.right,memo));
        int res = Math.max(money, count(node.left, memo) + count(node.right, memo));
        memo.put(node, res);
        return res;
    }

    public int[] countPlus(TreeNode node){
        //TODO 这个方法真的秀
        if (node == null) return new int[2];
        int[] res = new int[2];

        int[] left = countPlus(node.left);
        int[] right = countPlus(node.right);

        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);//当前节点不偷，结果储存儿子偷或不偷的最大值
        res[1] = left[0] + right[0] + node.val;//当前节点偷，返回子节点不偷的值

        return res;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}